/*
 * @lc app=leetcode.cn id=1575 lang=cpp
 *
 * [1575] 统计所有可行路径
 */

// @lc code=start
class Solution
{
    int f[105][205], modNum = 1e9 + 7, n;

public:
    int getResult(int s, int e, int r, vector<int> &locations)
    {
        if (f[s][r] != -1)
            return f[s][r];

        if (s == e)
            f[s][r] = 1;
        else
            f[s][r] = 0;

        for (int i = 0; i < n; i++)
        {
            if (s == i)
                continue;
            int diff = abs(locations[s] - locations[i]);
            if (diff > r)
                continue;
            f[s][r] += getResult(i, e, r - diff, locations);
            f[s][r] %= modNum;
        }

        return f[s][r];
    }

    int countRoutes(vector<int> &locations, int start, int finish, int fuel)
    {
        n = locations.size();
        // 初始化为 -1， 表示未访问
        memset(f, -1, sizeof(f));

        return getResult(start, finish, fuel, locations);
    }
};
// @lc code=end
